import java.util.Arrays;

public class MergeSort {
    private MergeSort() {
    }

    public static <E extends Comparable<E>> void sort(E[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    public static <E extends Comparable<E>> void sort(E[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = (l + r) / 2;
        sort(arr, l, mid);
        sort(arr, mid + 1, r);
        merge(arr, l, mid, r);
    }

    public static <E extends Comparable<E>> void sort2(E[] arr) {
        sort2(arr, 0, arr.length - 1);
    }

    public static <E extends Comparable<E>> void sort2(E[] arr, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = (l + r) / 2;
        sort2(arr, l, mid);
        sort2(arr, mid + 1, r);
        //优化代码逻辑，当mid>mid-1的时候再合并
        if (arr[mid].compareTo(arr[mid - 1]) > 0) {
            merge(arr, l, mid, r);
        }

    }

    public static <E extends Comparable<E>> void sort3(E[] arr) {
        sort3(arr, 0, arr.length - 1);
    }

    public static <E extends Comparable<E>> void sort3(E[] arr, int l, int r) {
        if (l - r <= 15) {
            sort4(arr, l, r);
            return;
        }
        int mid = (l + r) / 2;
        sort3(arr, l, mid);
        sort3(arr, mid + 1, r);
        //优化代码逻辑，当mid>mid-1的时候再合并
        if (arr[mid].compareTo(arr[mid - 1]) > 0) {
            merge(arr, l, mid, r);
        }

    }

    public static <E extends Comparable<E>> void sort4(E[] arr, int l, int r) {
        for (int i = l; i <= r; i++) {
            //将arr[i]插入到合适的位置
//            for (int j = i; j - 1 >= 0; j--) {
//                //每次和之前一位的值比较
//                if (arr[j].compareTo(arr[j - 1]) < 0) {
//                    swap(arr, j, j - 1);
//                } else {
//                    break;
//                }
//            }
            for (int j = i; j - 1 >= l && arr[j].compareTo(arr[j - 1]) < 0; j--) {
                swap(arr, j, j - 1);
            }
        }
    }

    //合并两个有序的区间
    private static <E extends Comparable<E>> void merge(E[] arr, int l, int mid, int r) {
        //将原数组从l到r+1的区间复制一份出来
        E[] temp = Arrays.copyOfRange(arr, l, r + 1);
        // mid代表右分区的开始
        int i = l, j = mid + 1;

        //每轮循环为arr[k]赋值
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                arr[k] = temp[k - l];
            } else if (j > r) {
                arr[k] = temp[i - l];
                i++;
            } else if (temp[i - l].compareTo(temp[j - l]) <= 0) {
                //arr[i]和arr[j]
                arr[k] = temp[i - l];
                i++;
            } else {
                arr[k] = temp[j - l];
                j++;
            }
        }
    }

    private static <E> void swap(E[] arr, int i, int j) {
        E temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
